Lamping, J. and Rao, R., "The Hyperbolic Browser: A Focus+Context Technique for Visualizing Large Hierarchies", Journal of Visual Languages and Computing, Vol. 7, 1996, pp. 33-55, disclose techniques for presenting trees, and discuss whether the same techniques can be extended to visualize more general graph structures. To solve the problem of crossing links, a graph could be converted to a tree by making a breadth-first traversal of the graph, copying each graph node for each incoming edge, so that each edge goes to its own copy of the node. The children of the node are attached only to one of the copies, referred to as the main node. The other copies of the node can be presented differently than the main node, such as with a different colored background. When one of the other copies is selected by the user, an animated transition can move the main copy of the node into focus. An alternative approach would be to give all copies of a node a copy of the descendant hierarchy. Lamping et al., U.S. Pat. No. 5,590,250, similarly mentions a variation in which node-link data defining all web pages of a network could be obtained by converting the web pages to a tree using an appropriate pruning constraint.
Munzner, T., and Burchard, P., "Visualizing the Structure of the World Wide Web in 3D Hyperbolic Space", in Proceedings of the VRML '95 Symposium (San Diego, Calif., Dec. 13-16, 1995), ACM SIGGRAPH, 1995, pages 33-38 and 138, disclose that, although the World Wide Web is non-linear, a tree can be imposed starting at any document, with the chosen node the root, each outgoing link a first-generation child, the links in these documents grandchildren, and so on. Munzner et al. also disclose techniques based on laying out an exhaustive subtree of a graph in standard hyperbolic space. The choice of an exhaustive subtree corresponds to choosing a root node and, for each other node, one incoming edge. Taking the tree that would be obtained by navigating out from the root node and attaching all children, a subtree can be selected by choosing a traversal order for the tree and then only retaining the first copy of each graph node.
Beaudet et al., U.S. Pat. No. 5,515,487, disclose selective display of portions of graphs by expanding and collapsing nodes in trees, directed acyclic graphs, and cyclic graphs, while retaining information concerning all node interconnections so that information can be correctly recalled as required. Nodes are selected for modification, all nodes connected to each selected node are assigned to a first set of nodes, and then each node is removed from the first set of nodes and assigned to a second set, together with any connected nodes that are not in the first set. The identified nodes are deleted from the display, and each node connected to a deleted node is highlighted, surrounded by an outline box, shown with outgoing arcs, or otherwise shown in a way that distinguishes collapsed nodes.
The invention addresses problems in using trees to represent graphs that are not trees, referred to herein as "non-tree graphs". Some previous techniques, including those described by Lamping and Rao and also by Munzner and Burchard, convert a graph to a tree, possibly resulting in a loss of information about some nodes and links. Other previous techniques, exemplified by Beaudet et al., U.S. Pat. No. 5,515,487, retain information about a graph even though the graph is modified for display, such as by deleting nodes connected to a node selected by a user, but do not provide a way to automatically present a tree representing a non-tree graph.
The invention provides techniques that alleviate these problems. The techniques provide node-link data defining both a graph and a tree within the graph. Defining the "elements" of the graph to include all of its nodes and links, a tree is "within" a graph if all the elements of the tree represent elements of the graph, with some elements of the graph possibly represented more than once in the tree. The node-link data include tree defining data that indicate, for each of a set of elements in the graph, whether the element is represented in the tree. In addition, a subset of the elements of the graph are represented more than once in the tree. For at least one element in the subset, the tree defining data indicate which of its representations are expanded and which are contracted; the term "expanded" is used here to mean that a representation of an element in the tree has one or more descendants, in contrast to a "contracted" representation of the element, which has no descendants in the tree even though it could based on the structure of the graph.
Tree defining data as described above make it possible to automatically present a tree representing a non-tree graph; specifically, the tree defined by the tree defining data can be presented, such as on a display. If the graph includes a cycle, for example, the tree defining data can indicate that an element in the cycle is represented in the tree, yet avoid infinite branches in the tree by indicating that certain representations of the element in the tree have no descendants.
One technique according to the invention provides an especially simple solution to the problem of cycles. This technique maintains the tree defining data so that at most one representation of an element in the graph is expanded in the tree. As a result, a downward path from the root node of the tree cannot include more than two occurrences of the element, ensuring that a cycle through the element in the graph will not cause problems in the tree.
Another technique according to the invention addresses the problem of reducing the size of the tree defining data in the case of a directed graph or another graph that can be treated as a directed graph. The technique defines a tree within the graph simply by indicating an appropriate set of links. In effect, each link in the set can be represented by a link in the tree, and nodes occur in the tree only where links meet, forming a tree of links. Besides its usefulness in obtaining a representation of a graph, a tree of links defined in this way could be used to mathematically derive the tree's characteristics.
Tree defining data according to this technique can, for example, be implemented as expansion/contraction data indicating, for each link in the set of elements, whether the link representing it in the tree leads to a node, referred to as its "to-node", that is expanded. If the to-node is expanded, the tree also includes links representing the outgoing links of the to-node in the graph. Thus, the expansion/contraction data define the set of links in the tree by indicating, for each link in the set, whether the outgoing links of its to-node are in the set. As used herein, expansion/contraction data "indicate a link is expanded" if the data indicate that the outgoing links of its to-node are in the set, while expansion/contraction data "indicate a link is contracted" if the data indicate that the outgoing links of its to-node are not in the set.
Following this technique, a version of the tree can be produced in which each node in the graph is represented once in the tree for each of its incoming links in the set. Nodes in the graph with more than one incoming link in the set will be represented more than once in the tree. This version can then be used to produce a representation of the graph as a tree.
The two techniques described above can be combined to elegantly ensure that the expansion/contraction data for at most one incoming link of any node in the graph indicate that the node's representation is expanded in the tree, the expansion/contraction data for the node's other incoming links all indicating that the node's representation is contracted in the tree. As a result, a downward path from the root node of the tree cannot include more than two occurrences of the node.
The new techniques are advantageous because they can be used to obtain a tree that represents a non-tree graph, while retaining information about the graph that is not reflected in the tree. For example, the new techniques can be used to automatically present a tree that represents a non-tree graph.
Because they preserve the data defining the underlying graph, the new techniques can also be used in a variety of situations in which it is desirable to present a number of different trees, each representing the graph differently. For example, if a user requests that a node in the tree be expanded or contracted, the expansion/contraction data can be modified so that a different tree is defined in the graph, with the node expanded or contracted as requested. The different tree can then be presented on a display.
The following description, the drawings, and the claims further set forth these and other aspects, objects, features, and advantages of the invention.